package com.ljy.my_study.leetcode.串联字符串的最大长度;

import java.util.*;

public class TestMain2 {

    /**
     * 回溯+位运算，二进制中每一位代表每个字母
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(new TestMain2().maxLength(Arrays.asList(new String[]{"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"})));
        Collections.sort(new ArrayList<Integer>(),(a,b)->{return a;});
    }

    public int maxLength(List<String> arr) {
        List<Integer> masks=new ArrayList<>();
        for(String s:arr){
            int mask=0;
            for(int i=0;i<s.length();i++){
                int num=1<<(s.charAt(i)-'a');
                if((mask&num)==0){
                    mask|=num;
                }else{
                    mask=0;
                    break;
                }
            }
            if(mask!=0){
                masks.add(mask);
            }
        }
        return dfs(masks,0,0,0);
    }

    private int dfs(List<Integer> masks,int index,int mask,int count){
        int newCount=count;
        if(index==masks.size()){
            return count;
        }
        if((mask&masks.get(index))==0){
            int num=mask|masks.get(index);
            newCount=Math.max(newCount,dfs(masks,index+1,num,Integer.bitCount(num)));
        }
        newCount=Math.max(newCount,dfs(masks,index+1,mask,Integer.bitCount(mask)));
        return newCount;
    }
}
